package leetcode_jz_offer.day14_sousuoAndHuisu;

/**
 * 地上有一个m行n列的方格，从坐标[0,0]到坐标[m-1,n-1]。
 * 一个机器人从坐标[0,0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
 * 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 **/
public class Num13_机器人的运动范围 {
    //通过递归实现的深度优先遍历
    //找上下左右是否能满足条件，注意定义二维数组表示当前位置是否被遍历过了
    public int movingCount(int m, int n, int k) {
        if(k==0){
            return 1;
        }
        boolean[][] visited=new boolean[m][n];
        int res=dfs(0,0,m,n,k,visited);
        return res;
    }
    //递归：能走到的格子数
    private int dfs(int i,int j,int m,int n,int k,boolean[][] visited){
        //1.递归出口条件：越界、位数和过大和已经访问过三种情况,此时没有可以走到的格子，返回0
        if(i<0||i>=m||j<0||j>=n||(sum(i)+sum(j))>k||visited[i][j]==true){
            return 0;
        }
        //2.更新当前状态，就是记录i,j格子为已访问状态
        visited[i][j]=true;
        //3.解决子问题:上下左右能返回的个数，返回子问题的解
        //+1是表示加上了当前[i,j]这个格子
        return 1+dfs(i-1,j,m,n,k,visited)+dfs(i+1,j,m,n,k,visited)+dfs(i,j-1,m,n,k,visited)+dfs(i,j+1,m,n,k,visited);
    }
    //位数和的计算
    private int sum(int i){
        int sum=0;
        while (i>0){
            sum+=i%10;
            i/=10;
        }
        return sum;
    }

//    //ps:visited也可以设置成全局变量
//    boolean[][] visited;
//    public int movingCount(int m, int n, int k) {
//        visited=new boolean[m][n];
//        int res=dfs(0,0,m,n,k);
//        return res;
//    }
//    private int dfs(int i,int j,int m,int n,int k){
//        //1.递归出口条件：越界、位数和过大和已经访问过三种情况,此时没有可以走到的格子，返回0
//        if(i<0||i>=m||j<0||j>=n||(sum(i)+sum(j))>k||visited[i][j]==true){
//            return 0;
//        }
//        //2.更新当前状态，就是记录i,j格子为已访问状态
//        visited[i][j]=true;
//        //3.解决子问题:上下左右能返回的个数，返回子问题的解
//        //+1是表示加上了当前[i,j]这个格子
//        return 1+dfs(i-1,j,m,n,k)+dfs(i+1,j,m,n,k)+dfs(i,j-1,m,n,k)+dfs(i,j+1,m,n,k);
//    }
//    //位数和的计算
//    private int sum(int i){
//        int sum=0;
//        while (i>0){
//            sum+=i%10;
//            i/=10;
//        }
//        return sum;
//    }
}
